#include<stdio.h>
#include<stdlib.h>

void _MergeSort(int* a, int left ,int right ,int*tmp)
{
     if(left>=right)//如果头大于或等于就代表以后递归到最后一个节点
     {
         return;
     }
    int mid=(left+right)/2;//中间节点的元素

    // 左[left][mid]        右[mid+1][left]-->递归的区间
    _MergeSort(a,left,mid,tmp);//左边
    _MergeSort(a,mid+1,right,tmp);//右边

    int began1=left,end1=mid;//[left][min]   左半区间
    int began2=mid+1,end2=right;//[right][right]  右半区间

    int index=left;
    while(began1<=end1&&began2<=end2)//开始归并
    {
        if(a[began1]<=a[began2])
        {
            tmp[index++]=a[began1++];//began1区间小插入到tmp中
        }
        else
        {
            tmp[index++]=a[began2++];//began2区间小插入到tmp中
        }
    }


    //一个数组的元素可能是还没有全部插入后续插入
    while(began1<=end1)//began相同时代表还有一个元素
    {
        tmp[index++]=a[began1++];
    }
    while(began2<=end2)
    {
        tmp[index++]=a[began2++];
    }

    //吧零时数组里面的值给原来数组
    for(int i =0;i<=right;i++)//传上来待n是下标不是元素个数
    {
        a[i]=tmp[i];
    }
}

void MergeSort(int* a, int n)
{
    int* tmp=(int*)malloc(sizeof(int)*n);//开辟一块空间后续方便插入
    _MergeSort(a,0,n-1,tmp);//头，尾，数组
}